package category;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

public class Algorithm {
    public static void main(String[] args) {
        Algorithm algorithm = new Algorithm();
        int[] nums = new int[]{1, 2, 3, 1, 2, 3, 7, 1, 7, 10};
        String alone = algorithm.findAloneC(nums);
        System.out.println(alone);
    }


    /**
     * 冒泡算法
     */
    public int[] bobble(int[] arr) {
        int n = arr.length - 1;
        for (int i = 0; i < n; i++)
            for (int j = n; j > i; j--)
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
        return arr;
    }

    /**
     * 模拟加法
     */
    public String addition(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int i = num1.length() - 1, j = num2.length() - 1;
        while (i >= 0 || j >= 0) {
            int digit1 = i < 0 ? 0 : num1.charAt(i--) - '0';
            int digit2 = j < 0 ? 0 : num2.charAt(j--) - '0';
            int sum = digit1 + digit2 + carry;
            carry = sum / 10;
            result.append(sum % 10);
        }
        if (carry > 0)
            result.append(carry);
        return result.reverse().toString();
    }

    /**
     * 乘法
     */
    public String multiplication(String num1, String num2) {
        int[] result = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + result[i + j + 1];
                result[i + j + 1] = mul % 10;
                result[i + j] += mul / 10;
            }
        }
        StringBuilder strRes = new StringBuilder();
        result = result[0] == 0 ? Arrays.copyOfRange(result, 1, result.length) : result;
        for (int res : result)
            strRes.append(res);
        return strRes.toString();
    }

    /**
     * 从整形数组中寻找出现单次的数字 时间：O(n),O(n平方) 空间：O(1)
     */
    public String findAlone(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            boolean flag = true;
            for (int j = 0; j < nums.length; j++) {
                if (i != j && nums[i] == nums[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return nums[i] + "";
            }
        }
        return "num is same";
    }


    /**
     * 从整形数组中寻找出现单次的数字 时间：O(n+1),O(2n) 空间：O(n)
     */
    public String findAloneB(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey() + "";
            }
        }
        return "num is same";
    }

    /**
     * 从整形数组中寻找出现单次的数字 时间：O(n+1),O(2n) 空间：O(n)
     */
    public String findAloneC(int[] nums) {
        int unique = 0;
        for (int num : nums) {
            unique ^= num;
        }
        return unique + "";
    }
}
